package dp.leetcode_337_medium_treedp;

import java.util.HashMap;
import java.util.Map;

public class Rob {
    //暴力递归
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //偷当前节点（爷爷节点），最大金额为 当前节点金额 + 孙子节点金额
        int curMoney = root.val;
        if (root.left != null) {
            curMoney += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            curMoney += rob(root.right.left) + rob(root.right.right);
        }
        //不偷当前，最大金额为 孩子节点的和
        int childMoney = rob(root.left) + rob(root.right);

        //两者取更大的就是能偷到的最大金额。
        return Math.max(curMoney,childMoney);
    }
    /**
     * 优化一：记忆化递归（去掉重复子问题）
     * 递归解法存在的问题：
     *      当孩子节点作为爷爷节点时，会重新计算孩子节点的最大金额，而此孩子节点在上一个过程已经被计算过。
     *      3
     *     / \
     *    4   5         3作为爷爷节点取得最大金额为：max( 孩子节点(4+5), 孙子节点(1+3+1) + 爷爷节点(3) );
     *   / \   \        当4、5作为爷爷节点时，还会计算孩子节点（1，3，1），而此过程在之前已经被计算过
     *  1   3   1
     *
     *
     * 由于是二叉树结构，使用数组将无法准确设置数组大小，故使用哈希表来充当缓存。
     *      将当前节点root作为key，其取得的最大金额作为V
     *      如果哈希表存在此root所计算出的最大金额，直接使用。
     */
    public int rob2(TreeNode root){
        Map<TreeNode,Integer> memory = new HashMap<>();
        return robMemory(root,memory);
    }
    public int robMemory(TreeNode root, Map<TreeNode,Integer> memory){
        if(root == null){
            return 0;
        }
        if(memory.containsKey(root)){
            return memory.get(root);
        }
        int curMoney = root.val;
        if(root.left != null){
            curMoney += robMemory(root.left.left,memory) + robMemory(root.left.right,memory);
        }
        if (root.right != null){
            curMoney += robMemory(root.right.left,memory) + robMemory(root.right.right,memory);
        }
        int res = Math.max(curMoney, robMemory(root.left,memory) + robMemory(root.right,memory));
        memory.put(root,res);
        return res;
    }
}


















